package lib;

import java.util.Arrays;
import java.util.LinkedList;

/**
 * 
 * @author  Igor Covganet
 * @Created Jul 21, 2010
 * 
 * The methods in this class are tested and work well.
 */
public class BipartiteMatching {
	public int[] lefts = null, rights = null;
	
	/** The matched nodes from left will have the index of node from right. The non-matched nodes will have the value -1 assigned. */
	public void bestMatch(boolean[][] matches) {
		int m = matches.length;
		int n = m > 0 ? matches[0].length : 0;
		
		lefts = new int[m];
		rights = new int[n];
		
		Arrays.fill(lefts, -1);
		Arrays.fill(rights, -1);
		// make the initial match
		for (int i = 0; i < lefts.length; i++) {
			for (int j = 0; j < rights.length; j++) {
				if(rights[j] >= 0 || !matches[i][j]) {
					continue;
				}
				
				lefts[i] = j;
				rights[j] = i;
				break;
			}
		}
		
		// find augmenting path
		boolean vb = true;
		while(vb) {
			vb = false;
			
			for(int i = 0; i < lefts.length; i++) {
				if(lefts[i] >= 0) {
					continue;
				}
				
				boolean[] used = new boolean[lefts.length];
				used[i] = true;
				LinkedList<LinkedList<Integer>> q = new LinkedList<LinkedList<Integer>>();
				for(int j = 0; j < rights.length; j++) {
					if(matches[i][j]) {
						LinkedList<Integer> list = new LinkedList<Integer>();
						list.add(j);
						q.add(list);
						used[rights[j]] = true;
					}
				}
				
				while(q.size() > 0 && !vb) {
					LinkedList<Integer> path = q.removeFirst();
					int val = rights[path.getLast()];
					for(int j = 0; j < rights.length; j++) {
						if(matches[val][j]) {
							if(rights[j] == -1) {
								// augmenting path found!!
								int last = path.removeFirst();
								lefts[i] = last;
								for(int y : path) {
									lefts[rights[last]] = y;
									last = y;
								}
								lefts[val] = j;
								for(int k = 0; k < m; k++) {
									if(lefts[k] != -1) {
										rights[lefts[k]] = k;
									}
								}
								vb = true;
								break;
							} else if(!used[rights[j]]) {
								LinkedList<Integer> tmp = new LinkedList<Integer>();
								for(int y : path) {
									tmp.add(y);
								}
								tmp.add(j);
								q.add(tmp);
								used[rights[j]] = true;
							}
						}
					}
				}
			}
		}
	}
}
